Data processing systems are more and more designed using a plurality of building blocks that communicate to each other via data links using a standardized protocol. Errors may occur in the communication. In particular a mobile phone is a noisy environment. The expected bit error rates are in the order of 10−12 which translates into one error every 15-20 minutes. As a result the communication protocol must detect and be able to recover from such errors.
U.S. Pat. No. 6,181,704 describes a method for transmitting data in a network from a transmitter to a receiver. Each of the transmitted data frames is assigned a corresponding sequence number. A copy of each data frame is stored in a buffer at the transmitter until an acknowledgment is received that each data frame was successfully received by the intermediary point. Once a particular data frame is successfully received by the receiver, the particular data frame is acknowledged to the transmitter, and is subsequently de-allocated at the transmitter, as are any other data frames in the buffer between the particular data frame and the previously last acknowledged data frame. Upon receipt of an error indication, the data frame indicated in the error indication is retransmitted along with all subsequent data frames. At the receiving end, all received data frames following the data frame associated with the error indication are dropped until successfully receiving a retransmitted version of the data frame. In addition, a single negative acknowledgment is used to indicate that a data frame associated with the negative acknowledgment includes at least one error and to simultaneously indicate that all previous data frames received prior to the data frame associated with the negative acknowledgment were received correctly.
As the transmitter maintains a copy of the transmitted data frames in its buffer until they are successfully transmitted, it cannot accept new data frames. Accordingly the data stream will be substantially delayed, if the number of errors is (temporarily) high.
It is a purpose of the present invention to provide for a reasonable protection against errors while providing real-time guarantees.
According to embodiments of the present invention only the newest data frames are stored in the retransmission buffer. If a new data frame is produced it overwrites the oldest data frames in as far as necessary. This measure is based on the observation that for a real-time application old data frames are not usable anymore (e.g., modem I/O samples, or video frames). Moreover, these old data frames can delay newer data frames that may still be usable directly after production, but not after a delay.
It is noted that the earlier Application IB2006/054240 filed by the same Applicant describes a data processing system that has a retransmission buffer for temporarily keeping data frames available for retransmission if they are not correctly received the first time. In this earlier filed Application however, the data frames are transmitted in fixed time slots. In the method described in the present application that is not necessary, as the data frames have sequence numbers. Furthermore, the retransmission buffer described in the earlier filed Application stores the data frames for a fixed duration. In the method and transmitter according to the present invention the data frames are kept in the retransmission buffer until it is necessary to overwrite them by a new data frame.
The receiver may acknowledge every correctly received data frame. However, this requires that a return link is maintained permanently activated. On the other hand if acknowledgments are omitted a transmitter cannot discriminate between the situation where an error message was sent, but not received, and the situation where no error message was transmitted.
In one embodiment the transmitter receives as a reminder a further error message if it did not provide a response to the error message sent first. Accordingly, each time the receiver transmits a negative acknowledgement message, it determines whether it receives a response within a predetermined time-limit and/or after counting a predetermined number of further errors. If no response is received before the time limit and/or before the limit in the number of errors, the receiver transmits a second error message. At the side of the transmitter this means that ambiguities are counter-acted, as the transmitter can expect a second error message if it missed an earlier error message and could not respond. Accordingly the use of positive acknowledgement messages becomes superfluous. In particular in case of relatively low error rates this enables a significant reduction of power of the return data link.
If the receiver has received no response to its second error message it may send further messages while waiting a predetermined time for the transmitters' response.
The transmitter may merely indicate that it has received the error message from the receiver. In one embodiment however, the transmitter retransmits the data frame for which it received an error message. In this way the data link from the transmitter to the receiver is used efficiently.
If the receiver does not receive a response to its error message, this may be caused by an out of sync condition of the data link (return data link) from the receiver to the transmitter. One embodiment provides for a resynchronization that overcomes this condition. The resynchronization may take place immediately when an error condition is detected in the verification step. However, taking into account that errors may occur incidentally, the resynchronization of the return data link may alternatively take place when the receiver detects that it has received no response to its first error message. Although resynchronization could be postponed until the second error message or even the further error message does not give a response, this is not preferred as already the absence of a response to the first error message is an indication of a more structural problem.
Likewise the occurrence of an error in a data frame received by the receiver may indicate that the data link from the transmitter to the receiver is in an out of sync condition. A repeated situation wherein the receiver does not receive a response from the transmitter may be due to an out of sync condition of the data link from the transmitter to the receiver. One embodiment overcomes this condition. A resynchronization may be initiated immediately after an error is detected, or may be postponed until it is more likely that the error is caused by an out of sync condition, preferably when sending the second error message.
The receiver may indicate with flow control messages, how many data frames it is prepared to receive. However, taken into account that these messages will load the return data link, in one embodiment the flow control messages are not sent. Although this may occasionally result in a situation where the transmitter sends more data frames than the receiver can handle this need not be a problem. In particular for real-time applications, dropping the non-accepted data frames allows the receiver to receive the remaining data frames without significant delay. In one embodiment those frames for which the receiver has insufficient storage space are dropped. In an embodiment an error message is returned to the transmitter when a data frame is dropped.
Likewise, the power consumption of the return data link can be reduced by avoiding acknowledgement messages from the receiver.
Various alternatives are possible for dropping data frames. A device having a buffer for temporarily storing data frames preferably drops the oldest of the messages stored in its buffer.
In addition to the user data and the sequence number, the data frames preferably have some redundant information to facilitate a verification of the data frames, for example in the form of cyclic redundancy check (CRC) data. The redundant information may be used in addition to correct errors, so that a retransmission is not always necessary. Alternatively errors may be detected for example by the occurrence of data having an out of bound value, or by detecting the occurrence of sequence numbers that are out of order.
In the above description it is presumed that it is the role of the transmitter to transmit data frames to the receiver, while the receiver merely sends error messages if appropriate. However, in an alternative embodiment, the return data link from the receiver to the transmitter may be used to transmit data from the receiver to the transmitter. Also in this embodiment the present invention is favorable, as by avoiding transmission of acknowledgement messages to the transmitter more bandwidth is available for transmission of data frames.
The data link for transmission of the data frames may be implemented in various ways. For example, the data link may be a serial or a parallel link. The data link may itself apply a coding. For example, the data may be transmitted with an embedded clock e.g. using 8bl0b encoding. Alternatively data and clock may be transmitted separately.
A transmitter according to the invention is claimed in claim 15.
A data processing system comprising a transmitter is claimed in claim 17.